(1) Field of the Invention
The present invention relates to an apparatus and a method for an orthogonal transform, a quantization, and an entropy coding of images and a medium recording a program for these coding processes, and relates to an apparatus and a method for an inverse transform and the decoding of a compressed code sequence which is obtained after the orthogonal transform, quantization, and entropy coding, and a recoding medium for recording a program for these decoding processes.
(2) Description of the Related Art
In recent years, techniques for decoding images which have been coded and compressed with high efficiency have been extensively developed and used in various fields, such as computers, communications, and broadcasts. Joint Photographic Coding Experts Group (JPEG) is recommended as an international standard for the compression coding and expansion decoding of images and Moving Picture Experts Group 1 (MPEG 1) Video is recommended as an international standard for the decoding of movies.
With these methods, image information is divided into blocks, each of which is composed of a certain number of pixels. Each pixel in the blocks is subjected to the orthogonal transform, quantization, and entropy coding to generate codes (or sometimes referred to as Huffman codes). The generated codes are combined and, construct a compression code sequence (or referred to simply as a code sequence). Codes in the compression code sequence are subjected to the entropy decoding, dequantization, and inverse orthogonal transform to generate an original image.
It should be noted here that, in the following description, the process for subjecting each pixel to the orthogonal transform, quantization, and entropy coding is referred to as a compression coding (or referred to simply as a coding) to be distinguished from the entropy coding. Also, the process for subjecting codes to the entropy decoding, dequantization, and inverse transform is referred to as an expansion decoding (or referred to simply as a decoding) to be distinguished from the entropy decoding.
1. Operation for Compression Coding and Decoding
The following is a description of the operation for the compression coding and the expansion decoding which is base on the baseline method which is essential to an image coding apparatus and an image decoding apparatus supporting Discrete Cosine Transform (DCT) of JPEG. The following description uses an example where each of an image coding apparatus and an image decoding apparatus includes a general-purpose microcomputer.
1.1 Procedure for Compression Coding
(1) Outline of Operation Procedure for Compression Coding
The following is a description of the operation procedure for the compression coding, with reference to the drawings.
FIG. 1 is a flowchart showing the outline of the operation procedure for the compression coding which is based on the JPEG baseline method.
Initialization for coding control is performed and one or more marker codes prescribed by JPEG are outputted (Step S1901). A rectangular area called a block composed of 8×8 pixels is cut out of an image to be compressed and coded (Step S1902), each element in the cut-out block is subjected to the discrete cosine transform, namely one type of the orthogonal transform, DCT coefficients of 8 lines×8 columns are outputted (Step S1903), the outputted DCT coefficients are divided by their corresponding elements in a quantization table, and 64 quantized DCT coefficients are outputted (Step S1904). The process for dividing each DCT coefficient by its corresponding element in the quantization table is called a quantization. The quantized DCT coefficients are scanned in the order called a zigzag scan and are subjected to the entropy coding, namely one type of the transform coding, to output a compression code sequence in which an image is compressed (Step S1905). Whether this process is repeated for all blocks of the image to be compressed and coded is confirmed (Step S1906). If all blocks of the image have been subjected to this process, the compression coding process is completed; if not, the operation returns to Step S1902 and this process is commenced for the next block.
(2) Operation Procedure for Quantization
The following is a description of the operation procedure in the quantization step shown in FIG. 1 as Step S1904, with reference to the flowchart shown in FIG. 2.
The loop counter “i” for controlling the repetition of the quantization process is initialized to be set to the value “0” (Step S1911). A DCT coefficient S(i) and an element Q(i) in the quantization table, which each correspond to the value of the loop counter “i”, are loaded from the memory (Steps S1912 and S1913), S(i) is divided by Q(i), the division result is rounded to be normalized so that a quantized DCT coefficient Sq(i) is obtained (Step S1914), and the quantized DCT coefficient Sq(i) is stored in a memory (Step S1915). The loop counter “i” is incremented by one to quantize the next DCT coefficient (Step S1916), and whether all DCT coefficients in one block have been subjected to this process is confirmed using the value of the loop counter “i” (Step, S1917). If all DCT coefficients in one block have been subjected to this process, this quantization process is completed; if not, the operation returns to Step S1912 and remaining DCT coefficients are subjected to this quantization process.
(3) Operation Procedure for Entropy Coding
The following is a description of the operation procedure in the entropy coding step shown in FIG. 1 as Step S1905, with reference to the flowchart in FIG. 3.
A Sq(0), namely the quantized DCT coefficient of a DC component, is loaded from the memory and the DC component Sq(0) is subjected to the entropy coding (Steps S1921 and S1922). A loop counter “i” for controlling the repetition of the entropy coding process on the quantized DCT coefficients of AC components and a counter “nnnn” for counting each zero coefficient run are initialized to be set to the values “1” and “0,” respectively (Step S1923). A scan order “z” corresponding to the loop counter “i” is obtained using a zigzag function “Zig( )” for generating a scan order used to perform a zigzag scan on quantized DCT coefficients (Step S1924). Using the scan order “z,” a quantized DCT coefficient Sq(z) of an AC component is loaded from the memory (Step S1925) and whether the value of this loaded quantized DCT coefficient Sq(z) is zero is judged (Step S1926). If the value of the quantized DCT coefficient Sq(z) is zero, the zero coefficient run counter “nnnn” is incremented by one (Step S1931); if not, the value of the zero coefficient run counter “nnnn” and the quantized DCT coefficient Sq(z) are combined and subjected to the entropy coding (Step S1927), and the zero coefficient run counter “nnnn” is initialized to be set to the value “0” (Step S1928). The loop counter “i” is incremented by one (Step S1929) and whether this process has been performed on one block is judged using the value of the loop counter “i” (Step S1930). If this process has been performed on one block, the entropy coding is completed; if not, the operation returns to Step S1924 to continue this entropy coding.
1.2 Procedure for Expansion Decoding
To use compressed and coded images, these images need to be subjected to the expansion decoding. The following is a description of the procedure for the expansion decoding, with reference to the drawings.
(1) Outline of Operation Procedure for Expansion Decoding
FIG. 4 is a flowchart showing the outline of the expansion decoding which is based on the JPEG baseline method.
Initialization for control of expansion decoding is performed and each marker code included in a compression code sequence is analyzed (Step S1941). The compression code sequence is subjected to the entropy decoding, namely one type of the transform coding, and 64 quantized DCT coefficients corresponding to one block are obtained (Step S1942). The obtained quantized DCT coefficients are multiplied by their corresponding elements in a quantization table to obtain DCT coefficients corresponding to one block (Step S1943). The obtained DCT coefficients corresponding to one block are subjected to the inverse discrete cosine transform (Step S1944), an original image in one block is restored, the restored original image in one block is outputted to the memory storing decoded images in respective blocks, and a full-size original image is reconstructed (Step S1945). Whether this process has been performed on all blocks is confirmed (Step S1946). If this process has been performed on all blocks, this expansion decoding process is completed; if not, the process from the entropy coding to the image reconfiguration (Steps S1942 to S1945) is repeated on remaining blocks.
(2) Operation Procedure for Entropy Decoding
The following is a description of the entropy decoding step shown in FIG. 4 as Step S1942, with reference to the flowchart in FIG. 5.
One code in a compression code sequence in which an image is compressed is subjected to the entropy decoding to obtain the quantized DCT coefficient Sq(0) of a DC component (Step S1961), and the DC component Sq(0) is stored in a memory (Step S1962). A loop counter “i” for controlling the entropy decoding on the quantized DCT coefficients of AC components is initialized to be set to the value “1” (Step S1963). The next code in the compression code sequence is subjected to the entropy decoding and the value of a zero run length “nnnn” and the quantized DCT coefficient of an AC component are obtained (Step S1964). An index “Z” which is used for a zigzag scan and corresponds to the loop counter “i” is obtained using a zigzag function Zig(i) (Step S1965) and the loop counter “i” is incremented by one (Step S1966). Whether the zero run length “nnnn” is zero is confirmed (Step S1967). If the zero run length “nnnn” is not zero, a value “0” is set as the quantized DCT coefficient Sq(z) of an AC component (Step S1970), Sq(z) having the value “0” is stored in the memory (Step S1971), the zero run length “nnnn” is decremented by one (Step S1972), and the process flow returns to Step S1965. If the zero run length “nnnn” is zero, the AC component Sq(z) is stored in the memory (Step S1968) and whether one block has been subjected to this process is confirmed using the value of the loop counter “i” (Step S1969). If the value of the loop counter “i” is 64, the process is judged to have been performed on one block and this entropy decoding process is completed; if not, the process is not judged to have been performed on one block, and the operation returns to Step S1964 to continue the entropy decoding.
(3) Operation Procedure for Dequantization
The following description concerns the operation procedure in the dequantization step shown in FIG. 4 as Step S1943, with reference to the flowchart in FIG. 6.
A loop counter “i” for controlling the repetition of the dequantization process is initialized to be set to the value “0” (Step S1951). A quantized DCT coefficient Sq(i) and an element Q(i) in the quantization table, which each correspond to the value of the loop counter “i”, are loaded from the memory (Steps S1952 and S1953), the quantized DCT coefficient Sq(i) is subjected to the dequantization using S(i)=Sq(i)×Q(i) to calculate a DCT coefficient S(i) (Step S1954), and the DCT coefficient S(i) is stored in the memory (Step S1955). The loop counter “i” is incremented by one to perform the dequantization on the next quantized DCT coefficient (Step S1956) and whether one block has been subjected to this process is confirmed using the value of the loop counter “i” (Step S1957). If the value of the loop counter “i” is 64, this process is judged to have been performed on one block and the dequantization process is completed; if not, this process is not judged to have been performed on one block and the process flow returns to Step S1952 to continue this dequantization process.
1.3 Order of Zigzag Scan
FIG. 7 shows the order of a zigzag scan during the process of the entropy coding and entropy decoding. In this figure, 64 circles represent quantized DCT coefficients or DCT coefficients. The white circle represents a DC component and 63 black circles represent AC components (AC1 to AC63). The numbers attached to the lower right of the circles and arrows show the order of the zigzag scan. The zigzag scan is repeated in the order of right, lower left, under, upper right, and then right.
FIG. 8 is a table showing the relation between the element number “i” of a quantized DCT coefficient or a DCT coefficient and the zigzag function Zig(i) which gives an order of the zigzag scan and corresponds to the element number “i”.
With the process procedure described above, an image is compressed and coded with efficiency, and a compression code sequence representing a compressed and coded image is expanded and decoded.
2. Entropy Decoding Process
The following is a detailed description of the entropy decoding of a code in Steps S1961 and S1964 in the flowchart of the entropy decoding process shown in FIG. 5.
Each code is made up of a bit sequence including two types of bits “0” and “1” and corresponds to one decode value. The structure of the bit sequence making up a code is determined by the fixed length code method or the variable length code method. With the fixed length code method, all codes have the same code length; with the variable length code method, each code has different code length.
Note that in the following description, codes have variable length, if not otherwise stated.
In the case of the variable length code method, on the assumption that the code length of a code having the longest code length is one word, address spaces each of which is 2 raised to the word length power are prepared in a conventional code sequence entropy decoding apparatus. The conventional code sequence entropy decoding apparatus is provided with a decode table. The decoding table is searched using a bit sequence as long as one word starting from the entropy decoding start position to obtain a corresponding decode value. With this method, the entropy decoding can be performed at high speed. However, as the longest code sequence length becomes longer, the size of the decode table becomes larger. As a result, there is a problem that more memory capacity is required, which increases the cost of the apparatus.
To solve this problem, Japanese Laid-Open Patent Application No. 6-44039 discloses an apparatus where the size of the decode table is reduced. The following description concerns the principle of the entropy decoding, the structure of the decode table, and the procedure for the entropy decoding, which are disclosed in Japanese Laid-Open Patent Application No. 6-44039.
2.1 Principle of Entropy Decoding
The following is a description of the principle of the entropy decoding disclosed in Japanese Laid-Open Patent Application No. 6-44039. As can be seen from FIG. 9, a plurality of variable length codes are divided into groups, where each group includes codes having the same run. Here, the run is a sequence of same bits from the start of each variable length code. With regard to all variable length codes 2087 whose run lengths are “6,” each 2-bit sequence following the run is the same bit sequence “11” (this same bit sequence will be hereinafter referred to as an identical bit sequence). As shown in the figure, each variable length code 2087 in the group of the run length “6” has a unique part which follows the run and the identical bit sequence (this unique part will be hereinafter referred to as an evaluation bit pattern) Therefore, this evaluation bit pattern represents its corresponding variable length code in the group of the run length “6.” This principle can be applied to other groups of the run lengths which are not “6.”
As described above, because a set of a run length, the length of an identical bit, and an evaluation bit pattern represents a certain variable length code, a decoding table can be made using this characteristic.
It should be noted here that the group of the run length “4” in FIG. 9 includes variable length codes of different lengths. The setting manner of the evaluation bit patterns in this group is described later.
2.2 Structure of Decoding Table
The following is a description of the structure of the decoding table which is based on the above-mentioned entropy decoding principle. As shown in FIG. 10, the decoding table is composed of the primary decoding table 2300 and the secondary decoding table 2310.
The primary decoding table 2300 is a two-dimensional data table storing a plurality of sets which are each composed of a shift amount 2302, an evaluation bit pattern length 2303, and an offset 2304. Each run length 2301 is a bit length of a run and is also used as an address specifying one of the plurality of sets in a line of the primary decoding table 2300. Each shift amount 2302 is a run length plus a length of an identical bit sequence. Each evaluation bit pattern length 2303 gives a bit length of an evaluation bit pattern. Each offset 2304 gives a value related to the addressing in the secondary decoding table 2310 described later. Each addition value calculated by adding an offset 2304 to an evaluation bit pattern is an address specifying a decode value in a line of the secondary decoding table 2310.
The secondary decoding table 2310 is a two-dimensional table storing pairs of a decode value 2314 and a code length 2315. Each address 2311 is an addition value obtained by adding an offset 2304 to an evaluation bit pattern and is also used as an address specifying a decode value 2314 in a line of the secondary decoding table 2310. Each decode value 2314 corresponds to a variable length code and is obtained by performing the entropy decoding on the variable length code. Each code length 2315 is a bit length of a variable length code.
In the case of quantized DCT coefficients of AC components of JPEG, each decode value 2314 is made up of two values, that is, a zero run length and a non-zero coefficient value.
2.3 Procedure for Entropy Decoding
The following description concerns the procedure for the entropy decoding of variable length codes using the primary decoding table 2300 and the second decoding table 2310 shown in FIG. 10. The entropy decoding is the transformation of a code extracted from a code sequence into its corresponding decode value. In this description, the variable length code “0000 0011 011” 2086 is extracted from the code sequence of “0000 0011 011 . . . ” and is subjected to the entropy decoding.
Because the run length of the variable length code 2086 is “6,” the primary decoding table 2300 is searched using this run length “6” as an address to obtain its corresponding values, that is, the shift amount “8” 2302, the evaluation bit pattern “3” 2303, and the offset “A6” 2304. Because the shift amount is “8,” the head bit position of the evaluation bit pattern 2085 is detected at the position where the variable length code 2086 is shifted to the left by 8 bits from its head bit. Because the evaluation bit pattern length is “3,” the evaluation bit pattern 2085 is determined to be “011.” The determined evaluation bit pattern “011” 2085 is added to the offset “A6” to obtain the corresponding address in the secondary decoding table. The secondary decoding table 2310 is searched using the obtained address and the decode value “10” 2314 is obtained.
FIGS. 11 and 28 show respectively the primary decoding table and the secondary decoding table for the decoding apparatus disclosed in Japanese Laid-Open Patent Application No. 6-44039. Because the bit width of the shift amount column is 4 bits, the bit width of the evaluation bit pattern column is 4 bits, the bit width of the offset column is 8 bits, and there are seven types of runs, the size of the primary decoding table is 112 bits calculated from (4 bits+4 bits+8 bits)×7 types. It should be noted here that each run length is an address value in the primary decoding table so that the run length column is not included in the size of this table. Because the bit width of the decode value column is 8 bits, the bit width of the code length column is 4 bits, and there are 55 types of decode values, the size of the secondary decoding table is 660 bits calculated from (8 bits+4 bits)×55 types.
3. Problems in the Conventional Techniques
As described above, an original image is compressed and coded with high efficiency to obtain a compression code sequence, and the compression code sequence is decoded to generate the original image.
However, this image processing for the image compression coding and image decoding needs a very large amount of operations, so that a general-purpose microcomputer will require a long time for this image processing. This is because a large number of memory load and store operations need to be performed due to the very large amount of data of an image, and because many operations which require a long processing time are used in this image processing.
This processing time is conventionally shortened by replacing a general-purpose microcomputer with special hardware or a digital signal processor. However, these devices are high-priced, resulting in the increased cost of products.